翻訳と辞書 Words near each other ・ Constraint (mathematics) ・ Constraint algebra ・ Constraint algorithm ・ Constraint automaton ・ Constraint Composite Graph ・ Constraint counting ・ Constraint Grammar ・ Constraint graph ・ Constraint graph (layout) ・ Constraint Handling Rules ・ Constraint inference ・ Constraint learning ・ Constraint logic programming ・ Constraint programming ・ Constraint satisfaction ・ Constraint satisfaction dual problem ・ Constraint satisfaction problem ・ Constraint-based Routing Label Distribution Protocol ・ Constraint-induced movement therapy ・ Constraints accounting ・ Constricta ・ Constricta (fungus) ・ Constricted elimia ・ Constricting Rage of the Merciless ・ Constriction ・ Constriction of video ・ Constriction ring syndrome ・ Constrictive pericarditis ・ Constrictivity ・ Constrictor Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Constraint satisfaction dual problem ： ウィキペディア英語版 Constraint satisfaction dual problem The dual problem is a reformulation of a constraint satisfaction problem expressing each constraint of the original problem as a variable. Dual problems only contain binary constraints, and are therefore solvable by algorithms tailored for such problems. The join graphs and join trees of a constraint satisfaction problem are graphs representing its dual problem or a problem obtained from the dual problem removing some redundant constraints. ==The dual problem== The dual problem of a constraint satisfaction problem contains a variable for each constraint of the original problem. Its domains and constraints are built so to enforce a sort of equivalence to the original problem. In particular, the domain of a variable of the dual problem contains one element for each tuple satisfying the corresponding original constraint. This way, a dual variable can take a value if and only if the corresponding original constraint is satisfied by the corresponding tuple. The constraints of the dual problem forbid two dual variables to take values that correspond to two incompatible tuples. Without these constraints, one dual variable may take the value corresponding to the tuple $x=1,y=2$ while another dual variable takes the value corresponding to $y=3,z=1$, which assigns a different value to $y$. More generally, the constraints of the dual problem enforce the same values for all variables shared by two constraints. If two dual variables correspond to constraints sharing some variables, the dual problem contains a constraint between them, enforcing equality of all shared variables. In the dual problem, all constraints are binary. They all enforce two values, which are tuples, to agree on one or more original variables. The ''dual graph'' is a representation of how variables are constrained in the dual problem. More precisely, the dual graph contains a node for each dual variable and an edge for every constraint between them. In addition, the edge between two variables is labeled by the original variables that are enforced equal between these two dual variables. The dual graph can be built directly from the original problem: it contains a vertex for each constraint, and an edge between every two constraints sharing variables; such an edge is labeled by these shared variables. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Constraint satisfaction dual problem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.